package OrderMap;

import java.util.Random;
import java.util.stream.IntStream;

public class SimpleSkipList {
    private final static byte head_node = -1;
    private final static byte data_node = 0;
    private final static byte tail_node = 1;

    private static class Node {
        private Integer value;
        private Node up, down, left, right;
        private byte bit;

        public Node(Integer value, byte bit) {
            this.value = value;
            this.bit = bit;
        }

        public Node(Integer value) {
            this(value, data_node);
        }
    }

    // 永远记录着最上层的头节点
    private Node head;
    // 永远记录着最上层的尾节点
    private Node tail;
    // 数据长度，也是最底层的节点个数
    private int size;
    private int height;
    private Random random;

    public SimpleSkipList() {
        this.head = new Node(null, head_node);
        this.tail = new Node(null, tail_node);
        head.right = tail;
        tail.left = head;
        this.random = new Random(System.currentTimeMillis());
    }

    private Node find(Integer element) {
        Node current = head;
        for (; ; ) {

            // 循环向右边找，直到，右边节点的值比我小
            while (
                    current.right.bit != tail_node && current.right.value <= element
            ) {
                current = current.right;
            }

            // 如果当前不是跳表“金字塔”的最底层，就向下走一层
            if (current.down != null) {
                current = current.down;
            } else {
                break;
            }
        }
        // the current <= element < current.right (if exist)
        return current;
    }

    public void dumpSkipList() {
        Node temp = head;
        for (int i = height; i >= 0; i--) {
            System.out.printf("Total [%d] height [%d]", height + 1, i + 1);
            Node node = temp.right;

            while (node.bit == data_node) {
                System.out.printf("->%d ", node.value);
                node = node.right;
            }

            System.out.print("\n");
            temp = temp.down;
        }
        System.out.println("==========================");
    }

    public boolean contains(Integer element) {
        Node node = this.find(element);

        return node.value.equals(element);
    }

    public void delete(Integer element) {
        Node node = find(element);
        if (node.value.equals(element)) {
            // 从下向上删除
            while (node != null) {
                node.left.right = node.right;
                node.right.left = node.left;

                node = node.up;
            }

            size--;
        }
    }

    public void add(Integer element) {
        Node nearNode = this.find(element);
        Node newNode = new Node(element);
        // 设置新节点和老节点的关系
        newNode.left = nearNode;
        newNode.right = nearNode.right;
        // 修改老节点
        nearNode.right.left = newNode;
        nearNode.right = newNode;

        int currentLevel = 0;
        while (random.nextDouble() < 0.3d) {
            // 超过当前的最大层高
            if (currentLevel >= height) {
                height++;

                Node dumyHead = new Node(null, head_node);
                Node dumyTail = new Node(null, tail_node);

                dumyHead.right = dumyTail;
                dumyHead.down = head;
                head.up = dumyHead;

                dumyTail.left = dumyHead;
                dumyTail.down = tail;
                tail.up = dumyTail;

                head = dumyHead;
                tail = dumyTail;
            }

            // 在上一层也添加这个新节点
            while ((nearNode.up == null)) {
                // 寻找当前节点上一层左边第一个节点
                nearNode = nearNode.left;
            }
            // 跳到上一层
            nearNode = nearNode.up;
            // 在nearNode右边添加当前节点
            Node upNode = new Node(element);
            upNode.left = nearNode;
            upNode.right = nearNode.right;
            upNode.down = newNode;

            nearNode.right.left = upNode;
            nearNode.right = upNode;

            newNode.up = upNode;

            newNode = upNode;
            currentLevel++;
        }

        size++;
    }

    public boolean isEmpty() {
        return (size() == 0);
    }

    public int size() {
        return size;
    }

    public static void main(String[] args) {
        SimpleSkipList simpleSkipList = new SimpleSkipList();
        IntStream.range(0, 20).forEach(simpleSkipList::add);
        simpleSkipList.dumpSkipList();
        System.out.println(simpleSkipList.size());
        IntStream.range(0, 10).forEach(simpleSkipList::delete);
        simpleSkipList.dumpSkipList();
        System.out.println(simpleSkipList.size());
    }
}